class EndException(Exception):
    pass

class Solution:
    def findItinerary(self, tickets):
        tiks = {}
        dsts = {}
        for src, dst in tickets:
            tik = src+dst
            if tik not in tiks: tiks.update({tik:0})
            tiks[tik]+=1
            if src not in dsts: dsts.update({src:set()})
            dsts[src].add(dst)
        for key in dsts:
            dsts[key] = sorted(dsts[key])
        
        path = []
        def traveral(src):
            print(src)
            path.append(src)
            end = True
            if src in dsts:
                for dst in dsts[src]:
                    tik = src+dst
                    if tik not in tiks: continue
                    elif tiks[tik]==0: continue
                    else:
                        tiks[tik]-=1
                        traveral(dst)
                        tiks[tik]+=1
                        end=False
            if end and len(path)==len(tickets)+1: raise EndException()
            path.pop()
        
        try:
            traveral("JFK")
        except EndException as e:
            pass
        return path
        
print(Solution().findItinerary([["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]))